|
In mathematical logic, a witness is a specific value ''t'' to be substituted for variable ''x'' of an existential statement of the form ∃''x'' φ(''x'') such that φ(''t'') is true. == Examples == For example, a theory ''T'' of arithmetic is said to be inconsistent if there exists a proof in ''T'' of the formula "0=1". The formula I(''T''), which says that ''T'' is inconsistent, is thus an existential formula. A witness for the inconsistency of ''T'' is a particular proof of "0 = 1" in ''T''. Boolos, Burgess, and Jeffrey (2002:81) define the notion of a witness with the example, in which ''S'' is an ''n''-place relation on natural numbers, ''R'' is an ''n''-place recursive relation, and ↔ indicates logical equivalence (if and only if): ::" ''S''(''x''1, ..., ''x''''n'') ↔ ∃''y'' ''R''(''x''1, . . ., ''x''''n'', ''y'') :" A ''y'' such that ''R'' holds of the ''xi'' may be called a 'witness' to the relation ''S'' holding of the ''xi'' (provided we understand that when the witness is a number rather than a person, a witness only testifies to what is true)." In this particular example, B-B-J have defined ''s'' to be ''(positively) recursively semidecidable'', or simply ''semirecursive''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Witness (mathematics)」の詳細全文を読む スポンサード リンク
|